package sword.chapter6Stack;

import java.util.Stack;

/**
 * 直方图最大矩形面积
 * min
 * j-i+1
 * 面积 = min * (j-i+1)
 * <p>
 * 单调栈
 * 栈中元素存值   输入值的下标 间接代表柱高
 * 辅助的数据结构  无
 * 什么时候入栈   满足单调递增，栈顶的柱高小于当前遍历的柱高
 * 什么时候出栈   不满足单调递增，栈顶出栈，并计算以栈顶为柱高的矩形面积
 * 面积计算：j-i+1 i是出栈后再peek的下标 => 上一个单调递增的矮柱子下标 一定可以保证出栈后的柱高，是这个下标之后的最高的柱子。因为单调递增，高的都被清掉了
 * 哨兵 直方图最左-1 最右直方图长度
 * <p>
 * 细节
 * 第一次遍历完以后，还要计算栈中的元素
 * 面积计算规律一样的，j=最右直方图长度
 *
 * @author K
 * @date 2021/12/4 14:46
 */
public class S39LargestRectangleArea {


    /**
     * 时间杂度O(n) 空间复杂度O(n)
     */
    public static int largestRectangleArea(int[] heights) {
        //用栈存柱子的下标，并保持栈中的柱子高度是递增的
        Stack<Integer> stack = new Stack<>();
        //栈中先存入一个柱子，当栈中无柱子时，它代表一个较矮的柱子
        stack.push(-1);

        int maxArea = 0;
        //从左向右遍历直方图，依次找到每个柱子作为矩形高度时的面积，即要找到左右两侧比栈顶柱子矮的柱子
        for (int i = 0; i < heights.length; i++) {
            //stack.peek() != -1表示栈中还有实际的柱子，并且当前柱子比栈顶柱子矮时
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                //此时表示找到了栈顶左右两侧均比它矮的最近的柱子，栈顶柱出栈（保证栈单调递增）
                int height = heights[stack.pop()];
                //若stack.peek() == -1，即左侧没有比它矮的柱子，则宽度直接从头计算，-(-1)即可
                Integer prevShortIndex = stack.peek();// 上一个单调递增的矮柱子下标
                int width = i - prevShortIndex - 1;
                //以栈顶的柱子为高度时的矩形面积，是两侧均比它矮的最近的柱子距离作为宽度与它高度的乘积
                int tempArea = height * width;// 高为栈顶的面积
                maxArea = Math.max(maxArea, tempArea);
            }
            //当前柱子比栈顶柱子高时，没有找到栈顶右侧的矮柱，入栈。
            stack.push(i);
        }

        //遍历结束后若栈中还有柱子，继续计算
        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            //每个柱子右侧没有比它矮的柱子，宽度直接从heights.length计算
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        return maxArea;
    }

    /**
     * 暴力法 O(n2)
     */
    public static int s39(int[] heights) {
        int result = 0;
        for (int i = 0; i < heights.length; i++) {
            int min = heights[i];
            for (int j = i; j < heights.length; j++) {
                min = Math.min(min, heights[j]);
                result = Math.max(result, min * (j - i + 1));
            }

        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints = {3, 2, 5, 4, 6, 1, 4, 2};
        int result = s39(ints);
        int result2 = largestRectangleArea(ints);
        System.out.println();
    }
}
